#include <dbg.h>

#include <cassert>

using namespace std;

class Solution {
public:
    int maximizeWin(vector<int>& prizePositions, int k) {
        int n = prizePositions.size();
        if (2 * k + 1 >= prizePositions[n - 1] - prizePositions[0]) {
            return n;
        }
        int res = 0;
        int left = 0;
        vector<int> mx(n + 1);
        for (int right = 0; right < n; right++) {
            while (prizePositions[right] - prizePositions[left] >
                   k) {  // 右移左端点，保证区间长度不超过 k
                ++left;
            }
            res = max(res, right - left + 1 + mx[left]);       // 计算答案
            mx[right + 1] = max(mx[right], right - left + 1);  // 更新前缀最大值
        }
        return res;
    }
};

int main() {
    Solution s;

    vector<int> prizePositions1 = {1, 1, 2, 2, 3, 3, 5};
    vector<int> prizePositions2 = {1, 2, 3, 4};

    int k1 = 2;
    int k2 = 0;

    assert(s.maximizeWin(prizePositions1, k1) == 7);
    assert(s.maximizeWin(prizePositions2, k2) == 2);

    return 0;
}